package labuladong.第四章;

import java.util.Arrays;

public class Prime {
    public static void main(String[] args) {
//        countPrime1();
        countPrime2(12);
    }

    private static void countPrime1() {
        int count = 0;
        for(int i=2; i<=10; i++) {
            if(isPrime(i))
                count++;
        }
        System.out.println(count);
    }

    public static boolean isPrime(int num) {
        for(int i=2; i<=Math.sqrt(num); i++){
            if(num%i == 0)
                return false;
        }
        return true;
    }

    public static void countPrime2(int num){
        boolean[] isPrime = new boolean[num];
        Arrays.fill(isPrime, true);

        for(int i=2; i*i<num; i++) {
            if(isPrime[i]) {
                for(int j=i*i; j<num; j+=i) {
                    isPrime[j] = false;
                }
            }
        }

        int count = 0;
        for(int i=2; i<num; i++){
            if(isPrime[i])
                count++;
        }
        System.out.println(count);
    }
}
